/* 375. 猜数字大小 II */
/**
 * @param {number} n
 * @return {number}
 */
/* dfs */
var getMoneyAmount = function (n) {
    if (n === 1) return 0
    /* dp[left][right]:表示 left ~ reight 区间 需要花费最小值 */
    const dp = new Array(n + 1).fill(0).map(_ => new Array(n + 1).fill(0))
    const dfs = (dp, left, right) => {
        if (left >= right) return 0
        if (dp[left][right] !== 0) return dp[left][right]
        let res = Number.MAX_VALUE
        for (let i = left; i <= right; i++) {
            /* 取最大值防止 不能玩 另一半 */
            const cost = i + Math.max(dfs(dp, left, i - 1), dfs(dp, i + 1, right))
            res = Math.min(res, cost)
        }
        dp[left][right] = res
        return res
    }
    return dfs(dp, 1, n)
};
const result = getMoneyAmount(2)
console.log('getMoneyAmount :>>', result);